Yao's minimax lemma

Theorem

Let $A$ be any random variable with values in set of deterministic algorithms $\mathcal{A}$ and let $X$ be any random variable with values in class of instances $\mathcal{X}$. Suppose $x \in \mathcal{X}$ and $a \in \mathcal{A}$ induce cost $c(a,x) \in \mathbb{R}$. Let $A$ be a randomized algorithm (now a random variable), then,

In other words, $A$'s worst-case expected cost is greater than or equal to the expected cost on random variable $X$ for the optimal algorithm.

Notes

• related to von Neumann's minimax theorem
• intuition: compare mixed strategies in a Nash game with randomized algorithms, algorithm is "playing" against worst-case (adversarial) input

References

1. A. C.-C. Yao, “Probabilistic computations: Toward a unified measure of complexity,” in 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), Providence, RI, USA: IEEE, Sept. 1977, pp. 222–227. doi: 10.1109/sfcs.1977.24.
2. https://faculty.cc.gatech.edu/~ssingla7/courses/Spring22/lec8.pdf
3. https://cstheory.stackexchange.com/questions/51591/trying-to-understand-the-intuition-behind-yaos-minimax-principle